package Hot100.Medium.GreedyAndDP.DynamicPlanning;

public class LC122_BuyMultipleStock {
    public static void main(String[] args) {

    }

    public int maxProfit(int[] prices){
        int len = prices.length;
        int res = 0;
        // 确定dp数组含义，在买卖股票中，dp[i][0]表示第i天持有股票所得的现金，dp[i][1]表示不持有股票所得的现金
        int[][] dp = new int[len][2];
        // 初始化dp数组，对于dp[0][0]表示第一天持有股票所得现金，也就是只能按照第一天价格买入
        // 对于dp[0][1]，表示第一天不持有股票所得现金，没买没卖，有0块钱
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        // 确定递推公式，与普通的买卖股票不同，本题可以在这些日子里买以及卖多次，因此对于dp[i][0],可以有两种方式推出
        // 第一种是跟前一天持有股票所得现金一致，也就是今天没再买，dp[i][0] = dp[i - 1][0]
        // 第二种是今天再买，因为一只股票可以买卖多次，所以当第i天买入股票的时候，所持有的现金可能有之前买卖过的利润。那就要用前一天不持有股票所得现金减去今天股票价格，这里与只能买卖一次不同。因此dp[i][0] = dp[i - 1][1] - prices[i]
        // 而对于dp[i][1]来说，也有两种方式推出，同样是前一天也不持有股票的钱以及，在第i天卖出股票的钱
        // 因此dp[i - 1][1]或者 prices[i] + dp[i - 1][0]
        for(int i = 1; i < len; i++){
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[len - 1][1];
    }
}
